/**
 * @file     trap.js
 * @brief    [42. 接雨水](https://leetcode.cn/problems/trapping-rain-water/)
 * @author   Zhu
 * @date     2024-11-28 17:30
 */

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
    const n = height.length;

    let ans = 0;
    const maxLeft = []; // maxLeft[i]表示i位置左侧最高的高度
    let tempMaxLeft = height[0];
    for (let i = 0; i < n; i++) {
        maxLeft[i] = tempMaxLeft = Math.max(height[i], tempMaxLeft);
    }

    const maxRight = [];
    let tempMaxRight = height[n - 1];
    for (let i = n - 1; i >= 0; i--) {
        maxRight[i] = tempMaxRight = Math.max(height[i], tempMaxRight);
    }

    for (let i = 0; i < n; i++) {
        const count = Math.min(maxLeft[i], maxRight[i]) - height[i];
        if (count > 0) ans += count;
    }

    return ans;
};

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
    const n = height.length;
    let ans = 0;

    const maxRight = [];
    let tempMaxRight = height[n - 1];
    for (let i = n - 1; i >= 0; i--) {
        maxRight[i] = tempMaxRight = Math.max(height[i], tempMaxRight);
    }

    let tempMaxLeft = height[0];
    for (let i = 0; i < n; i++) {
        tempMaxLeft = Math.max(height[i], tempMaxLeft);
        const count = Math.min(tempMaxLeft, maxRight[i]) - height[i];
        if (count > 0) ans += count;
    }

    return ans;
};

/**
 * 单调栈: 横着计算面积
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
    const n = height.length;
    let ans = 0;

    const stack = [];
    const top = () => stack[stack.length - 1];

    for (let i = 0; i < n; i++) {
        // [0,1,0,2,1,0,1,3,2,1,2,1]
        // 0,0  <- 1,1
        // 1,1  2,0  <- 3,2                  1*1
        // 3,2  4,1  5,0  <-  6,1         1*1
        // 3,2  6,1  <-  7,3                  1* 3
        // 7,3  8,2  9,1  <- 10,2        1*1
        // 7,3  11,1
        while (height[i] >= height[top()]) {
            const t = stack.pop();
            if (stack.length === 0) break; // 至少要两个墩儿才行
            const left = top();
            const w = i - left - 1;
            const h = Math.min(height[i], height[left]) - height[t];
            ans += w * h;
        }
        stack.push(i);
    }

    return ans;
};
